﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace testPrj
{

    class Pascal
    {
		/// <summary>
        /// Convert Integer To Roman string
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public static String IntToRoman(int num)
        {
            String[] digit = new String[] { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
            String[] ten = new String[] { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
            String[] hundred = new String[] { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
            String[] thousand = new String[] { "", "M", "MM", "MMM" };

            StringBuilder result = new StringBuilder();

            if (num > 3999)
            {
                num = 3999;
            }
            else if (num < 0)
            {
                num = 0;
            }

            result.Append(thousand[num / 1000]);
            result.Append(hundred[num / 100 % 10]);
            result.Append(ten[num / 10 % 10]);
            result.Append(digit[num % 10]);
            return result.ToString();

        }
		
        public void Test()
        {
            for (int i = 0; i < 100; ++i)
            {
                uint[] arr = Make(i);
                string s = string.Join(" ", arr.Select(e => e.ToString()).ToArray());
                Console.WriteLine(s);
            }
        }

        public uint[] Make(int n)
        {
            List<uint> current = null;
            if (n == 0)
            {
                current = new List<uint>() { 1 };
            }
            else
            {
                current = new List<uint>();
                uint[] last = Make(n - 1);
                uint z = 0;
                for (int i = 0; i < last.Length; i++)
                {
                    current.Add(z + last[i]);
                    z = last[i];
                }
                current.Add(z);
            }

            return current.ToArray();

        }

        public int[] Generate(int n)
        {
            List<int> current = null;
            if (n == 0)
            {
                current = new List<int>() { 1 };
            }
            else
            {
                current = new List<int>();
                List<int> last = new List<int>() { 1, 1 };
                for (int i = 0; i < n; ++i)
                {
                    current.Clear();
                    current.Add(last[0]);
                    for (int j = 0; j < i; j++)
                    {
                        current.Add(last[j] + last[j+1]);
                    }
                    current.Add(current[0]);
                    last.Clear();
                    last.AddRange(current);
                }
            }

            return current.ToArray();

        }
    }
}
